package com.dyz.leetcode._20_dynamicProgramming;

public class _53_maxSubArray {
    //暴力解法
    public int maxSubArray1(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j <nums.length ; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum+=nums[k];
                }
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
    //动态规划
    public int maxSubArray2(int[] nums){
        int n = nums.length;
        int[][] dp = new int[n][n];
        dp[0][0]=nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1]+nums[i];
            maxSum = Math.max(maxSum, dp[0][i]);

        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                dp[i][j] = dp[i-1][j]-dp[i-1][i-1];
                maxSum = Math.max(maxSum, dp[i][j]);
            }
        }
        return maxSum;
    }

    //动态规划+空间压缩
    public int maxSubArray(int[] nums){
        int n = nums.length;
        int[] dp = new int[n];
        dp[0]=nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1]+nums[i];
            maxSum = Math.max(maxSum, dp[i]);

        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                dp[j] = dp[j]-dp[i-1];
                maxSum = Math.max(maxSum, dp[j]);
            }
        }
        return maxSum;
    }
}
